import java.util.ArrayList;
import java.util.List;

/**
 * 1763. 最长的美好子字符串
 * https://leetcode-cn.com/problems/longest-nice-substring/
 */
public class Solutions_1763 {
    public static void main(String[] args) {
        String s1 = "YazaAay";  // output: "aAa"
        String s2 = "Bb";  // output: "Bb"
        String s3 = "c";  // output: ""
        String s4 = "dDzeE";  // output: "dD"

        List<String> inputs = new ArrayList<>();
        inputs.add(s1);
        inputs.add(s2);
        inputs.add(s3);
        inputs.add(s4);

        for (String input : inputs) {
            String result = longestNiceSubstring(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：暴力法
     */
    public static String longestNiceSubstring(String s) {
        String res = "";
        if (s == null) {
            return res;
        }
        int len = s.length();
        if (len < 2) {
            return res;
        }
        char[] arr = s.toCharArray();
        for (int i = 0; i < len; i++) {
            char match = (char) (arr[i] ^ 32);
            if (s.indexOf(match, i + 1) == -1) {
                // 后续没有与字符 arr[i] 对应的大小写字母
                continue;
            }
            boolean[] counts = new boolean[128];
            for (int j = i; j < len; j++) {
                counts[arr[j]] = true;
                if (j > i && check(counts) && j - i + 1 > res.length()) {
                    // 出现更长的美好字符串
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }

    /**
     * 1.有小写字母，无大写字母
     * 2.无小写字母，有大写字母
     * 以上两种可能都无法形成美好字符串
     */
    public static boolean check(boolean[] counts) {
        for (char i = 'a'; i <= 'z'; i++) {
            if (counts[i] && !counts[i - 32]) {
                return false;
            }
            if (!counts[i] && counts[i - 32]) {
                return false;
            }
        }
        return true;
    }
}
